【组合数学】排列组合 ( 多重集组合数 |
您所在的位置：网站首页 › a3 2 排列组合 › 【组合数学】排列组合 ( 多重集组合数 |
【组合数学】排列组合 ( 多重集组合数
|
文章目录一、多重集组合 ( 所有元素重复度大于组合数 )二、多重集组合 所有元素重复度大于组合数 推导 1 ( 分割线推导 )二、多重集组合 所有元素重复度大于组合数 推导 2 ( 不定方程非负整数解个数推导 ) 排列组合参考博客 : 【组合数学】基本计数原则 ( 加法原则 | 乘法原则 )【组合数学】集合的排列组合问题示例 ( 排列 | 组合 | 圆排列 | 二项式定理 )【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 )【组合数学】排列组合 ( 排列组合示例 )【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 )一、多重集组合 ( 所有元素重复度大于组合数 )多重集 : S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty元素种类 : 多重集中含有 k种不同的元素 , 元素表示 : 每个元素表示为 a_1 , a_2 , \cdots , a_k, 元素个数 : 每个元素出现的次数是 n_1, n_2, \cdots , n_k, 元素个数取值 : n_i的取值要求是 大于 0, 小于正无穷 + \infty; 上述多重集的组合 , 当 所有元素的重复度 n_i组大于组合数 r时 , r \leq n_i时 , 多重集的组合数为 N= C(k + r - 1, r)二、多重集组合 所有元素重复度大于组合数 推导 1 ( 分割线推导 )多重集 : S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty取 r种元素的组合 , r \leq n_i, 推导过程如下 :  在 k种元素中 , 取 r种元素 , 每种元素取 0 \sim r个不等的元素 , 使用 k-1个分割线分割 k种元素的位置 , k - 1个分割线相当于组成了 k个盒子 , 在每个盒子中放 0 \sim r个不等的元素 , 放置的总元素的个数是 r个 , 分割线个数是 k-1个 , 这里就产生了一个组合问题 , 在 k-1个分割线 和 r个元素之间 , 选取 r个元素 , 就是 多重集的 r \leq n_i情况下的 组合个数 ; 结果是 : N= C(k + r - 1, r)二、多重集组合 所有元素重复度大于组合数 推导 2 ( 不定方程非负整数解个数推导 )多重集 : S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty取 r种元素的组合 , r \leq n_i, 推导过程如下 : 多重集 S每个元素取值 : 第 1种元素取值个数 : 元素 a_1的取值个数是 x_1, 第 2种元素取值个数 : 元素 a_2的取值个数是 x_2, \; \; \, \ \ \ \ \ \ \vdots第 k种元素取值个数 :元素 a_k的取值个数是 x_k; 不定方程 x_1 + x_2 + \cdots + x_k = r; x_i可以为 0, 即某个元素取值个数可以是 0; 则多重集 S的 r组合是 : \{ x_1 \cdot a_1 , x_2 \cdot a_2 , \cdots , x_k \cdot a_k \}x_i的取值是非负整数 多重集组合与方程对应 : 只要有一个 r组合 , 就可以写出一个对象的 方程 x_1 + x_2 + \cdots + x_k = r出来 ; 非负整数解与多重集组合对应 : x_1 + x_2 + \cdots + x_k = r不定方程的一组非负整数解 , 就对应着 一个 S多重集的 r组合 ; 一一对应关系 : 上述 方程的非负整数解的个数 与 S多重集的 r组合个数 一一对应 ; 求 S多重集的 r组合数 , 就可以转化成 求 x_1 + x_2 + \cdots + x_k = r方程非负整数解个数 ; 将上述解写成一个序列 , 序列中使用 k-1个 0, 分割 k组 1; \begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_1个1 \end{matrix}0\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_2个1 \end{matrix}0\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_3个1 \end{matrix}0\cdots0\begin{matrix} \underbrace{ 1 \cdots 1 } \\ x_k个1 \end{matrix}不定方程每个解 都对应着 上述 k-1个 0和 r个 1的一个排列 ; 相当于一个多重集 S' = \{ r \cdot 1 , (k-1) \cdot 0 \}的全排列 ; 这里就将 多重集的组合问题 , 转化成了 另外一个多重集的全排列问题 , 多重集全排列是有公式的 ; 多重集全排列的公式是 : ( 回顾知识点 ① ) S = \{ n_1 \cdot a_1 , n_2 \cdot a_2 , \cdots , n_k \cdot a_k \} , \ \ \ 0 \leq n_i \leq +\infty★ 全排列 : r = n_1 + n_2 + \cdots + n_k = nN = \cfrac{n!}{n_1! n_2! \cdots n_k!}★ 多重集的全排列数是 元素总数阶乘 , 除以 所有重复度的阶乘 ; 参考 : 【组合数学】排列组合 ( 多重集排列 | 多重集全排列 | 多重集非全排列 所有元素重复度大于排列数 | 多重集非全排列 某些元素重复度小于排列数 ) 二、多重集全排列 ( 回顾知识点完毕 ① ) 可以根据上述公式 , 计算 多重集 S' = \{ r \cdot 1 , (k-1) \cdot 0 \}的全排列 , 结果是 : N = \cfrac{(r + k - 1) !}{ r! (k-1)! }★ 排列数与组合数回顾 : ( 回顾知识点 ② ) 排列数 : n元集 S, 从 S集合中 有序 , 不重复 选取 r个元素 , P(n,r) = \dfrac{n!}{(n-r)!}组合数 : n元集 S, 从 S集合中 无序 , 不重复 选取 r个元素 , C(n,r) = \dfrac{P(n,r)}{r!} \dfrac{n!}{(n-r)!r!}参考 : 【组合数学】排列组合 ( 排列组合内容概要 | 选取问题 | 集合排列 | 集合组合 ) ( 回顾知识点完毕 ② ) 由上述的组合数可以看出 , N = \cfrac{(r + k - 1) !}{ r! (k-1)! }的值正好是从 r + k - 1个元素中取 r个元素的组合数 ; N = \cfrac{(r + k - 1) !}{ r! (k-1)! } = C(r + k - 1 , r) |
【本文地址】
今日新闻 |
推荐新闻 |